package bm27;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/8/11 2:16
 * BM27. 按之字形打印二叉树
 * https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0?tpId=295&tqId=23454&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 */
public class Solution {

    // 层次遍历思路
    public ArrayList<ArrayList<Integer>> Print (TreeNode root) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>(); // 用于记录结果
        // 边界
        if (root == null) {
            return ret;
        }
        // 层序遍历思路
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        boolean flag = true; // 用于标记之字形的方向
        while (!queue.isEmpty()) {
            flag = !flag;
            int curSize = queue.size();
            ArrayList<Integer> curRes = new ArrayList<>(); // 记录每一层
            while (curSize-- != 0) {
                TreeNode pollNode = queue.poll();
                if (pollNode.left != null) {
                    queue.offer(pollNode.left);
                }
                if (pollNode.right != null) {
                    queue.offer(pollNode.right);
                }
                curRes.add(pollNode.val);
            }
            if (flag) {
                Collections.reverse(curRes); // 反转
            }
            ret.add(curRes);
        }
        return ret;
    }

    private class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }
}
